package tree;

import java.util.Stack;

/**
 * 题目： 判断两个二叉树是否相等
 *
 * @Author Gavin
 * @date 2021.12.08 22:10
 */
public class tree_2 {
    /**
     * 解题思路：
     *  1.递归判断二叉树的根节点是否想等，如果想等然后判断他们的左右子树是否想等，最后根节点为null的时候返回true
     *  2.使用一个stack来解决，
     */
    //第一种：使用递归的方式
    //Time:O(n) Space:O(n)
    public static boolean solution(TreeNode node1,TreeNode node2){
        if(node1==null&&node2==null)return true;
        if(node1==null||node2==null)return false;
        return node1.val==node2.val&&solution(node1.left,node2.left)&&solution(node1.right,node2.right);
    }
    //第二种方式，使用一个stack来解决
    //Time:O(n) Space:O(n)
    public static boolean solution2(TreeNode node1,TreeNode node2){
        Stack<TreeNode> stack=new Stack<>();
        stack.push(node1);
        stack.push(node2);
        while (!stack.isEmpty()){
            TreeNode p=stack.pop();
            TreeNode q=stack.pop();
            if(p==null&&q==null)continue;
            if(p==null||q==null)return false;
            if(p.val!=q.val)return false;
            stack.push(p.left);
            stack.push(q.left);
            stack.push(p.right);
            stack.push(q.right);
        }
        return true;
    }
}
